package java学习.去哪儿;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/7 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 花样运动员 {
    /**
     * dp[i]  i之前的最大价值
     * 01 背包 bagsize = energy ,
     * dp[i] max(dp[j],dp[j-w[i]]+vi )
     *
     */
    public static int maxScore (int energy, int[][] actions) {
        // write code here
        int []dp = new int [energy+1];
        int []w = new int[actions.length];
        int[] v = new int[actions.length];
        for (int i = 0; i < actions.length; i++) {
            w[i] = actions[i][0];
            v[i] = actions[i][1];

        }
        for (int i = 0; i <actions.length; i++) {
            for (int j = energy; j >=w[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[energy];
    }

    public static void main(String[] args) {
//
        int[][] test = {{1,1},{2,3},{3,5},{5,10},{7,9},{8,10}};
        System.out.println(maxScore(10,test));
    }
}
